/**
 * 线段树其实就是树状数组的完全版，主要用来维护【区间信息】的数据结构
 * 使用范围：单点修改、区间修改、区间查询（区间求和、区间求最大值、区间求最小值）
 */
#include <iostream>
using namespace std;
// 通常而言，MAX 的值大致需要是序列长度的 4 倍
const int MAX = 40000;
// 其中 tree数组用来 存储线段树，a 数组用来存储序列, mark 数组用来记录懒标记
int tree[MAX], a[MAX], mark[MAX];
// n 代表 a 数组元素个数
int n;
/**
 * @brief 标记下移操作
 *
 * @param p 当前节点
 * @param len
 */
void push_down(int p, int len) {
  // 标记下传
  mark[p << 1] += mark[p];
  mark[(p << 1) + 1] += mark[p];
  tree[p << 1] += mark[p] * (len - (len >> 1));
  tree[(p << 1) + 1] += mark[p] * (len >> 1);
  // 清除标记
  mark[p] = 0;
}

/**
 * @brief 建立线段树
 *
 * @param l 区间左边界
 * @param r 区间右边界
 * @param p 层次遍历线段树的节点编号
 */
void build(int l, int r, int p = 1) {
  // 边界条件：l == r
  if (l == r) {
    tree[p] = a[l];
    return;
  }

  int mid = ((r - l) >> 1) + l;
  build(l, mid, p << 1);
  build(mid + 1, r, (p << 1) + 1);
  tree[p] = tree[p << 1] + tree[(p << 1) + 1];
}

/**
 * @brief 区间修改
 *
 * @param l 修改区间的左边界
 * @param r 修改区间的右边界
 * @param k 修改值
 * @param cl 当前区间左边界
 * @param cr 当前区间右边界
 * @param p 当前节点
 */
void update(int l, int r, int k, int p = 1, int cl = 1, int cr = n) {

  if (cr < l || cl > r) { // 当前区间与目标区间没有交集
    return;
  } else if (cl >= l && cr <= r) { // 当前区间在目标区间范围内
    tree[p] += (cr - cl + 1) * k;
    // 如果不是叶子结点，那么则需要打上标记，如果是叶子绩点，那么就没有必要打上懒标记
    if (cr > cl)
      mark[p] += k;
  } else { // 当前区间与目标区间有交集
    int mid = ((cr - cl) >> 1) + cl;

    push_down(p, cr - cl + 1);

    // 递归向下搜寻
    update(l, r, k, p << 1, cl, mid);
    update(l, r, k, ((p << 1) + 1), mid + 1, cr);
    // 最后根据子节点的值更新当前节点
    tree[p] = tree[p << 1] + tree[(p << 1) + 1];
  }
}

/**
 * @brief 区间查询操作
 *
 * @param l 待查询区间的左边界
 * @param r 待查询区间的右边界
 * @param cl 当前区间左边界
 * @param cr 当前区间右边界
 * @param p 当前节点
 */
int query(int l, int r, int p = 1, int cl = 1, int cr = n) {
  if (cr < l || cl > r) {
    return 0;
  } else if (l >= cl && cr <= r) {
    return tree[p];
  } else {
    push_down(p, cr - cl + 1);
    int mid = ((cr - cl) >> 1) + cl;
    return query(l, r, p << 1, cl, mid) +
           query(l, r, (p << 1) + 1, mid + 1, cr);
  }
}
int main() {
  n = 5;
  for (int i = 1; i <= n; ++i) {
    a[i] = i;
  }

  // 建树
  build(1, 5);

  // 查询
  cout << query(1, 5) << endl;

  // 修改操作
  update(1, 5, 1);

  update(2, 4, 1);

  cout << query(1, 5) << endl;
  return 0;
}
